//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
//
// 
//
// 参考以下这颗二叉搜索树： 
//
//      5
//    / \
//   2   6
//  / \
// 1   3 
//
// 示例 1： 
//
// 输入: [1,6,3,2,5]
//输出: false 
//
// 示例 2： 
//
// 输入: [1,3,2,6,5]
//输出: true 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// 
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 333 👎 0


package leetcode.editor.cn1;

import com.leetcode.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

//Java：二叉搜索树的后序遍历序列
public class ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
        // TO TEST
        System.out.println(solution.verifyPostorder(new int[]{1,6,3,2,5}));
        System.out.println(solution.verifyPostorder(new int[]{1,3,2,6,5}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二叉搜索树的后序遍历序列
         * 后序遍历：左右根
         * 最后一个节点就是根节点
         * 二叉搜索树的特点：左 < 根 < 右
         *
         * @param postorder
         * @return
         */
        public boolean verifyPostorder(int[] postorder) {
            if (postorder.length == 0)
                return true;
            if (postorder.length == 1)
                return true;
            int plen = postorder.length;
            TreeNode root = null;
            for (int i = plen - 1; i >= 0; i--) {
                // 不断插入节点
                root = insertNode(root, postorder[i]);
            }
            // 开始进行后序遍历
            List<Integer> list = new ArrayList<>();
            dfs(root, list);

            // 开始一个个进行比较
            for (int i = 0; i < plen; i++) {
                if (postorder[i] != list.get(i))
                    return false;
            }
            return true;
        }

        public TreeNode insertNode(TreeNode node, int k) {
            if (node == null) {
                node = new TreeNode(k);
            } else {
                // 遍历node
                if (k > node.val) {
                    // 往node.right
                    node.right = insertNode(node.right, k);
                } else {
                    // 往node.left
                    node.left = insertNode(node.left, k);
                }
            }
            return node;
        }

        public void dfs(TreeNode node, List<Integer> list) {
            if (node != null) {
                dfs(node.left, list);
                dfs(node.right, list);
                list.add(node.val);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
